When massive calculation such as scientific calculation is performed by one or more computers, the calculation time can be reduced by performing the calculation by a plurality of computers in parallel. In the case where a plurality of computers perform parallel processing, the data communication efficiency between the computers greatly affects the overall processing efficiency. Therefore, the simple mesh or torus networks are considered for use as an interconnecting network realizing efficient data communication. In a system constituted by a plurality of computers, each computer is referred to as a node.
In the mesh network, nodes are respectively arranged at grid points on a grid (mesh) structure formed with the transmission lines. In the two-dimensional torus network, nodes located at opposite ends of the series of nodes arrayed along each of the longitudinal direction and the lateral direction on the mesh network are connected through transmission lines, respectively. In the mesh or torus networks, messages containing communication data are relayed by nodes in a manner like a bucket relay. In the bucket-relay communication, when each node receives a message, the node forwards the message to an adjacent node located on the destination side (i.e., performs routing). At this time, each node determines, by itself, a route through which the message can be transmitted most efficiently, and forwards the message through the determined route. For example, according to a known technique, each processor performing routing determines the next hop on the basis of the amounts of load imposed on processors surrounding the processor performing routing so that the amounts of load imposed on all the processors are equated. (See, for example, Japanese Laid-open Patent Publication No. 63-198150.)
Incidentally, in computer systems in which nodes are connected in a mesh or torus network, collective communication (e.g., one-to-many or many-to-many communication) can occur. Specifically, in the broadcast, scatter, and all-to-all communication processes, data is transmitted from one node to all the other nodes. In the broadcast process, identical message is transmitted to many nodes. The broadcast process can be completed by inserting preferable data in a message, and transmitting the message, for example, in a bucket-relay manner.
However, in the collective communications such as the scatter or all-to-all communication, a great number of messages are transmitted, so that congestion can occur in some communication path in the network. In the scatter communication, a node transmits individual data to each of a plurality of nodes. In the all-to-all communication, all nodes perform scatter communication. The scatter communication and the all-to-all communication are different from the broadcast communication in that unique messages are transmitted from each source to each destination. Hereinafter, the collective communications such as the scatter communication and the all-to-all communication are referred to as collective communication of unique-messages.
For example, when collective communication of unique-messages is performed in an n-parallel computer system constituted by n nodes arranged in a mesh or torus network, n bucket-relay transmitting operations occur in the scatter communication, and n2 bucket-relay transmitting operations occur in the all-to-all communication. Therefore, when massive data communication is randomly started, load concentration and congestion can occur in some communication path. When the congestion occurs, the time until completion of the collective communication increases. This problem becomes conspicuous in the all-to-all (many-to-many) communication.
Conventionally, no technique has been proposed for efficiently balancing communication loads which occur in collective communication of unique-messages performed in a parallel computer system constituted by a simple mesh or torus network. Therefore, load concentration often occurs in the conventional parallel computer systems constituted by a simple mesh or torus network when collective communication of unique-messages is performed.